package arithmetic.leetcode;

import java.util.Scanner;

/**
 * @author taffywen
 * @date 2022/4/29 22:54
 *
 * 将两个升序链表合并成一个新的升序链表。新链表是通过拼接给定的两个链表的所有节点组成
 */
public class Q5合并有序链表 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] strArry = s.split(",");

        String ss = scanner.nextLine();
        String[] strArry2 = ss.split(",");

        ListNode list1 = new ListNode();
        ListNode list2 = new ListNode();

        ListNode temp = list1;
        for (int i = 0; i < strArry.length; i++) {
            temp.next = new ListNode(Integer.parseInt(strArry[i]));
            temp = temp.next;
        }
        temp = list2;
        for (int i = 0; i < strArry2.length; i++) {
            temp.next = new ListNode(Integer.parseInt(strArry2[i]));
            temp = temp.next;
        }

        ListNode listNode = mergeTwoLists(list1.next, list2.next);
        while (listNode != null){
            System.out.print(listNode.val + "\t");
            listNode = listNode.next;
        }
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode  list2){
        if (list1 == null){
            return list1;
        }
        if (list2 == null){
            return list2;
        }
        ListNode result = new ListNode();

        ListNode temp = result;

        while (list1 != null && list2 != null){

            if (list1.val <= list2.val){
                // 如果把 temp = list1 ，那么temp指向就会一直在变，就不会更改result 的值
                temp.next = list1;
                list1 = list1.next;
            }else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        if (list1 != null){
            temp.next = list1;
        }
        if (list2 != null){
            temp.next = list2;
        }


        return result.next;
    }
}
